package com.hyb.algorithm.data.struct.window;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: ybhu
 * @create: 2021/09/19 19:57
 *
 * https://leetcode-cn.com/problems/3sum/ (高频老题）
 */
public class ThreeSum {


    //1、排序
    //2、三个指针  k i=left j=right
    //  如果 nums[k]>0  直接跳出   移动 i j
    //1、排序
    //2、三个指针  k i=left j=right
    //  如果 nums[k]>0  直接跳出   移动 i j
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);

        int n=nums.length;

        List<List<Integer>> retList=new ArrayList<>();
        for(int k=0;k<n-2;k++){
            if(nums[k]>0){
                continue;
            }
            // 因为是有序的 如果与上次相同 说明用过了
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }

            int sumRet=-nums[k];
            int i=k+1;
            int j=n-1;
            while(i<j){

                // 因为是有序的 如果与上次相同 说明用过了
                if(i>k+1&&nums[i]==nums[i-1]){
                    i++;
                    continue;
                }
                if(nums[i]+nums[j]>sumRet){
                    j--;
                    continue;
                }
                if(nums[i]+nums[j]<sumRet){
                    i++;
                    continue;
                }
                List<Integer> ret=new ArrayList<>();
                ret.add(nums[k]);
                ret.add(nums[i]);
                ret.add(nums[j]);
                retList.add(ret);
                i++;
                j--;
            }
        }
        return retList;
    }
}
